|
In structural complexity theory, the Berman–Hartmanis conjecture is an unsolved conjecture named after Leonard C. Berman and Juris Hartmanis that states that all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms.〔.〕〔.〕〔 〕〔.〕 ==Statement== An isomorphism between formal languages ''L''1 and ''L''2 is a bijective map ''f'' from strings in the alphabet of ''L''1 to strings in the alphabet of ''L''2, with the property that a string ''x'' belongs to ''L''1 if and only if ''f''(''x'') belongs to ''L''2. It is a polynomial time isomorphism (or ''p''-isomorphism for short) if both ''f'' and its inverse function can be computed in an amount of time polynomial in the lengths of their arguments. observed that all languages known at that time to be NP-complete were ''p''-isomorphic. More strongly, they observed that all then-known NP-complete languages were ''paddable'', and they proved (analogously to the Myhill isomorphism theorem) that all pairs of paddable NP-complete languages are ''p''-isomorphic. A language ''L'' is paddable if there is a polynomial time function ''f''(''x'',''y'') with a polynomial time inverse and with the property that, for all ''x'' and ''y'', ''x'' belongs to ''L'' if and only if ''f''(''x'',''y'') belongs to ''L'': that is, it is possible to pad the input ''x'' with irrelevant information ''y'', in an invertible way, without changing its membership in the language. Based on these results, Berman and Hartmanis conjectured that all NP-complete languages are ''p''-isomorphic.〔.〕 Since ''p''-isomorphism preserves paddability, and there exist paddable NP-complete languages, an equivalent way of stating the Berman–Hartmanis conjecture is that all NP-complete languages are paddable. Polynomial time isomorphism is an equivalence relation, and it can be used to partition the formal language into equivalence classes, so another way of stating the Berman–Hartmanis conjecture is that the NP-complete languages form a single equivalence class for this relation. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Berman–Hartmanis conjecture」の詳細全文を読む スポンサード リンク
|